import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 937. 重新排列日志文件
 * <a href="https://leetcode.cn/problems/reorder-data-in-log-files/">...</a><p>
 * User: DELL
 * Date: 2023-10-12
 * Time: 10:18
 */
public class Solution {
    private class Unit {
        String log;
        int index;

        public Unit(String log, int index) {
            this.log = log;
            this.index = index;
        }
    }

    /**
     * 解题思路:
     * 本题主要是利用重写比较器,来自定义比较方法,使得原日志可以按照特定方式排序.
     * 但是因为 sort() 底层是使用快排的,是不稳定的,因此若对应数字日志,就无法
     * 保证数字日志的相对顺序,因此这里自定义了一个类 Unit ,其中有两个字段,分别
     * 为 log 和 index,即日志和在原 logs 数组中的下标,因此此时在同为数字日志时,
     * 比较 index 字段即可.
     * 本题因为使用了 Java 的 sort() 函数,而其本身是不稳定的,因此没有办法引入了
     * 自定义类 Unit,这使得出现了很多看似冗余的步骤,即封装和拆封,本题也可以自定义
     * 稳定的排序方法将 logs 排序.
     * 稳定的排序方法 --- 冒泡排序+直接插入排序+归并排序+基数排序
     *
     * @param logs
     * @return
     */
    public String[] reorderLogFiles(String[] logs) {
        // 对原日志进行处理,记录其下标位置
        Unit[] units = new Unit[logs.length];
        for (int i = 0; i < logs.length; i++) {
            units[i] = new Unit(logs[i], i);
        }
        Arrays.sort(units, this::compare);
        // 将日志恢复出来
        for (int i = 0; i < logs.length; i++) {
            logs[i] = units[i].log;
        }
        return logs;
    }

    private int compare(Unit u1, Unit u2) {
        // 取出两个日志
        String log1 = u1.log;
        String log2 = u2.log;
        // 分割两个日志
        String[] temp1 = new String[2];
        String[] temp2 = new String[2];
        temp1 = log1.split(" ", 2);
        temp2 = log2.split(" ", 2);
        // 判断日志类型
        boolean isDigit1 = Character.isDigit(temp1[1].charAt(0));
        boolean isDigit2 = Character.isDigit(temp2[1].charAt(0));
        // 分类处理
        if (isDigit1 && isDigit2) {
            // 全是数字日志
            return u1.index - u2.index;
        } else if (isDigit1) {
            // log1 是数字日志, log2 是字母日志
            return 1;
        } else if (isDigit2) {
            // log2 是数字日志, log1 是字母日志
            return -1;
        } else {
            // 两个均是字母日志
            if (temp1[1].compareTo(temp2[1]) != 0) {
                // 日志内容不同
                return temp1[1].compareTo(temp2[1]);
            } else {
                // 日志内容相同,比较标识符
                return temp1[0].compareTo(temp2[0]);
            }
        }
    }
}